package com.sunny.排序.希尔排序;

import com.sunny.util.ArrayUtil;

public class ShellKnuthSort {
    public static int[] shellKnuthSort(int size) {
        // 开始时间
        long start = System.currentTimeMillis();
        // 初始化数组
        int[] array = ArrayUtil.instanceArray(size);
        // 排序
        int step = 1;
        int length = array.length;
        while(step < (length/3)) {
            step = step * 3 + 1;
        }

        while(step > 0) {
            // 分别对每个step进行插入排序
            for(int i = step; i < length; ++i) {
                int temp = array[i];
                int j = i;
                while(j >= step && temp <= array[j - step]) {
                    array[j] = array[j - step];
                    j -= step;
                }
                array[j] = temp;
            }
            step = (step - 1)/3;
        }
        // 结束时间
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));
        return array;
    }
}
